package 单调栈;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

// 503 下一个更大元素2
public class Solution3 {
    public int[] nextGreaterElements(int[] nums) {
        int[] res = new int[nums.length];
        Arrays.fill(res, -1);
        Deque<Integer> stack = new LinkedList();
        for (int i = 0 ; i < 2 * nums.length ; i++) {
            while (!stack.isEmpty() && nums[stack.getLast() % nums.length] < nums[i % nums.length]) {
                int top = stack.pollLast();
                if (top < nums.length)res[top] = nums[i%nums.length];
                //上面的if可以去掉一些重复赋值
            }
            stack.addLast(i);
        }
        return res;
    }
}
